package com.gyg.程序员面试金典;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */

/**
 * 面试题 04.04. 检查平衡性
 * 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
 * 解题思路：
 * 利用DFS进行深度优先搜索，同时利用递归求出问题的子问题，即求出每一个节点的高度，
 * 每一个节点的高度就等于它左子树和右子树的最大高度+1。
 * 定义一个全局变量来接收是否为平衡树，最后返回这个结果。
 * 如果左子树和右子树的高度差大于1，那么整个数一定不是平衡树，结果就是false
 */
public class T04_04 {
    //    （1）定义一个布尔型的变量，来接收节点是否是平衡的，如果哪个节点不平衡，就等于false
    boolean result = true;

    public boolean isBalanced(TreeNode root) {
//        （2）首先看二叉树是否是空的，如果是空的，一定是平衡的
        if (root == null) {
            return true;
        }
//（3）判断该二叉树是否是平衡的
        checkHerght(root);
//        返回最终结果
        return result;
    }

    /**
     * 递归算法
     * 求每一个子树的高度，
     *
     * @param roots
     * @return
     */
    public int checkHerght(TreeNode roots) {
//        （4）如果为空，说明该节点不存在，高度就是0
        if (roots == null) {
            return 0;
        }
//        （5）深搜左边的节点，返回左子树的高度
        int left_Height = checkHerght(roots.left);
//        （6）深搜右边节点，返回右边子树的高度
        int right_Height = checkHerght(roots.right);
//        （7）如果左子树和右子树的高度差大于1，说明不是平衡树
        if (Math.abs(left_Height - right_Height) > 1) {
//            （8）如果不是平衡的，就将结果变量变为false
            result = false;

        }
//        （9）返回当前节点的树的高度，子树的最大高度加上本身
        return Math.max(left_Height, right_Height) + 1;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
